import "sort"

func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{}
	list := []int{}
	m := make(map[int]bool)
	permuteUniqueHelper(&res, nums, list, m)
	return res
}
func permuteUniqueHelper(res *[][]int, nums []int, list []int, m map[int]bool) {
	if len(nums) == len(list) {
		tmp := make([]int, len(list))
		copy(tmp, list)
		*res = append(*res, tmp)
		return
	}

	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] && m[i-1] == false {
			continue
		}

		if _, ok := m[i]; !ok {
			m[i] = true
			list = append(list, nums[i])
			permuteUniqueHelper(res, nums, list, m)
			list = list[:len(list)-1]
			delete(m, i)
		}
	}
}

// @lc code=end

